import java.util.Arrays;

public class QuickSort {
    // 快速排序主函数
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 获取分区索引
            int pivotIndex = partition(arr, low, high);
            // 对左半部分递归排序
            quickSort(arr, low, pivotIndex - 1);
            // 对右半部分递归排序
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // 分区函数
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low]; // 以第一个元素为枢轴
        int left = low + 1;   // 左指针
        int right = high;     // 右指针

        while (left <= right) {
            // 左指针找到一个大于枢轴的元素
            while (left <= right && arr[left] <= pivot) {
                left++;
            }
            // 右指针找到一个小于枢轴的元素
            while (left <= right && arr[right] > pivot) {
                right--;
            }
            // 交换左指针和右指针的元素
            if (left < right) {
                swap(arr, left, right);
            }
        }
        // 交换枢轴与右指针位置的元素
        swap(arr, low, right);

        return right; // 返回枢轴最终位置
    }

    // 交换数组中的两个元素
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 主函数测试
    public static void main(String[] args) {
        int[] arr = {26, 5, 37, 1, 62, 11, 59, 15};
        System.out.println("排序前: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}
